Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return thekth(1-based) smallest product ofnums1[i] * nums2[j]where0 <= i < nums1.lengthand0 <= j < nums2.length.
Input: nums1 = [2,5], nums2 = [3,4], k = 2 Output: 8 Explanation: The 2 smallest products are: - nums1[0] * nums2[0] = 2 * 3 = 6 - nums1[0] * nums2[1] = 2 * 4 = 8 The 2nd smallest product is 8.
Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6 Output: 0 Explanation: The 6 smallest products are: - nums1[0] * nums2[1] = (-4) * 4 = -16 - nums1[0] * nums2[0] = (-4) * 2 = -8 - nums1[1] * nums2[1] = (-2) * 4 = -8 - nums1[1] * nums2[0] = (-2) * 2 = -4 - nums1[2] * nums2[0] = 0 * 2 = 0 - nums1[2] * nums2[1] = 0 * 4 = 0 The 6th smallest product is 0.
Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3 Output: -6 Explanation: The 3 smallest products are: - nums1[0] * nums2[4] = (-2) * 5 = -10 - nums1[0] * nums2[3] = (-2) * 4 = -8 - nums1[4] * nums2[0] = 2 * (-3) = -6 The 3rd smallest product is -6.
1 <= nums1.length, nums2.length <= 5 * 104-105 <= nums1[i], nums2[j] <= 1051 <= k <= nums1.length * nums2.lengthnums1andnums2are sorted.
importmathclassSolution: defkthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) ->int: iflen(nums2) <len(nums1): nums1, nums2=nums2, nums1lo=min(nums1[0] *nums2[0], nums1[0] *nums2[-1], nums1[-1] *nums2[0], nums1[-1] *nums2[-1]) hi=max(nums1[0] *nums2[0], nums1[0] *nums2[-1], nums1[-1] *nums2[0], nums1[-1] *nums2[-1]) whilelo<hi: mid= (lo+hi) //2count=0foriinrange(len(nums1)): ifnums1[i] ==0: count+=len(nums2) ifmid>=0else0elifnums1[i] >0: count+=bisect.bisect(nums2, mid//nums1[i]) else: count+=len(nums2) -bisect.bisect(nums2, math.ceil(mid/nums1[i]) -1) ifcount<k: lo=mid+1else: hi=midreturnhi